package dataStructure;

import sun.reflect.generics.tree.Tree;

public class BinaryTree {
    TreeNode head;

    /**
     * 增加元素
     * @param item
     */
    public void add(Integer item){
        TreeNode newNode = new TreeNode(item);

        if(head == null){
            head = newNode;
        } else{
            TreeNode cur = head;
            TreeNode pre = null;
            Boolean flag = true;
            while(cur != null){
                pre = cur;
                if(item <= cur.item){
                    cur = cur.leftChild;
                    flag = true;
                } else if(item > cur.item){
                    cur = cur.rightChild;
                    flag = false;
                }
            }
            if(flag == true){
                pre.leftChild = newNode;
            } else {
                pre.rightChild = newNode;
            }
        }
    }

    public void delete(Integer item){
        if(head == null){
            System.out.println("树为空，删除失败");
            return ;
        }
        TreeNode cur = head;
        TreeNode pre = null;
        boolean flag = true;
        while(cur != null){
            if(item < cur.item){
                pre = cur;
                cur = cur.leftChild;
                flag = true;
            } else if(item > cur.item){
                pre = cur;
                cur = cur.rightChild;
                flag = false;
            } else{
                if(flag == true){
                    pre.leftChild = null;
                } else{
                    pre.rightChild = null;
                }
                return;
            }
        }
        System.out.println("元素不存在");
        return ;
    }
    /**
     * 前序遍历
     */
    public void preOrder(){
        if(head == null){
            System.out.println("树为空，直接返回");
            return ;
        }
        preOrderImpl(head);
    }
    /**
     * 前序遍历实现(递归)
     */
    private void preOrderImpl(TreeNode cur){
        if(cur == null){
            return;
        }
        System.out.println(cur.item);
        preOrderImpl(cur.leftChild);
        preOrderImpl(cur.rightChild);
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(head == null){
            System.out.println("树为空，直接返回");
            return ;
        }
        midOrderImpl(head);
    }

    /**
     * 中序遍历实现(递归)
     * @param cur
     */
    private void midOrderImpl(TreeNode cur){
        if(cur == null){
            return;
        }
        midOrderImpl(cur.leftChild);
        System.out.println(cur.item);
        midOrderImpl(cur.rightChild);
    }

    /**
     * 后序遍历
     */
    public void aftOrder(){
        if(head == null){
            System.out.println("树为空，直接返回");
            return ;
        }
        aftOrderImpl(head);
    }

    /**
     * 后序遍历实现(递归)
     * @param cur
     */
    private void aftOrderImpl(TreeNode cur){
        if(cur == null){
            return ;
        }
        aftOrderImpl(cur.leftChild);
        aftOrderImpl(cur.rightChild);
        System.out.println(cur.item);
    }
}
